#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 415. 字符串相加.py
@time: 2022/1/7 17:28
@desc: https://leetcode-cn.com/problems/add-strings/
> 给定两个字符串形式的非负整数num1 和num2, 计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。

1. 按位相加，进位的管理要注意，取较长的作为n来遍历，将原数组反转来遍历，然后记录一个进位up，若最后up不为0就可以加入，最后再反转回去，就是结果
2. Ot(n), Os(n)

'''
class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        n = len(num1) if len(num1)<len(num2) else len(num2)
        num1 = num1[::-1]
        num2 = num2[::-1]
        res = []
        up = 0
        i = 0

        while i<n:
            sum = int(num1[i]) + int(num2[i]) + up
            if sum>9:
                sum = str(sum)
                up, s = int(sum[0]), sum[1]
            else:
                s = str(sum)
                up = 0
            res.append(s)
            i += 1

        while i<len(num1):
            sum = int(num1[i])+up
            if sum>9:
                sum = str(sum)
                up, s = int(sum[0]), sum[1]
            else:
                s = str(sum)
                up = 0
            res.append(s)
            i += 1

        while i<len(num2):
            sum = int(num2[i]) + up
            if sum>9:
                sum = str(sum)
                up, s = int(sum[0]), sum[1]
            else:
                s = str(sum)
                up = 0
            res.append(s)
            i += 1

        if up>0:
            res.append(str(up))
        res = res[::-1]
        return ''.join(res)

if __name__ == '__main__':
    res = Solution().addStrings('456','77')

